package __二叉树

/*
https://leetcode.cn/problems/find-bottom-left-tree-value/

513. 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

示例 1:
输入: root = [2,1,3]
输出: 1

示例 2:
输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7
*/
var sumDep int // 全局变量 最大深度
var res int    // 记录最终结果

func findBottomLeftValue(root *TreeNode) int {
	//初始化深度, 结果
	sumDep, res = 0, 0 // 初始化

	//root:根节点  1:深度
	dfs(root, 1)

	return res
}

func dfs(n *TreeNode, curDep int) {
	//如果当前节点为空, 直接返回即可
	if n == nil {
		return
	}

	//如果当前节点为叶子节点, 并且总深度计数 < 当前深度
	if n.Left == nil && n.Right == nil && sumDep < curDep {
		sumDep = curDep //更新总深度
		res = n.Val     //更新结果变量
	}

	//递归调用左右节点
	dfs(n.Left, curDep+1) // 隐藏回溯
	dfs(n.Right, curDep+1)
}
